package LearnDataStructure.d_图结构.d_二分图;

import LearnDataStructure.d_图结构.GraphNode_AdjacencyList;

import java.util.List;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-15 18:39
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.d_图结构.d_二分图
 */
public class e_BipartiteGraph {
    public static void main(String[] args) {
        GraphNode_AdjacencyList node1 = new GraphNode_AdjacencyList(1);
        GraphNode_AdjacencyList node2 = new GraphNode_AdjacencyList(2);
        GraphNode_AdjacencyList node3 = new GraphNode_AdjacencyList(3);
        GraphNode_AdjacencyList node4 = new GraphNode_AdjacencyList(4);

        node1.add(node2);
        node1.add(node4);

        node3.add(node2);
        node3.add(node4);

        node2.add(node1);
        node2.add(node3);

        node4.add(node1);
        node4.add(node3);

        e_BipartiteGraph test = new e_BipartiteGraph();
        System.out.println(test.judgeBipartiteGraph(node1,1));
    }

    public boolean judgeBipartiteGraph(GraphNode_AdjacencyList node, int color) {
        node.color = color;//先把node染色
        List<GraphNode_AdjacencyList> neighbors = node.getNeighbors();
        for (int i = 0; i < node.getSize(); i++) {
            GraphNode_AdjacencyList neighbor = neighbors.get(i);
            if (neighbor.color == color) {//如果邻居和node颜色相同，那么已经撞了，这个图肯定不是二分图
                return false;
            }
            if (neighbor.color == 0) {//邻居未染色
                boolean result = judgeBipartiteGraph(neighbor, -color);//判断当邻居染成反色，能不能成功
                if (!result) {//如果不能染成反色
                    return false;//那么这个图肯定不是二分图
                }
            }
        }
        //跳出循环，那么代表node染成color，是没问题的
        return true;//返回“node染色成功”
    }
}
